package com.lg.algorithm.lru;

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V> {
	
	/**
	 * 
	 */
	private static final long serialVersionUID = 1882839504956564761L;
	
	private int capacity;
	
	public LRULinkedHashMap(int capacity) {
		super(capacity,0.75f,true);
		this.capacity = capacity;
	}

	/**
	 * 重写remove方法
	 * @param eldest
	 * @return
	 */
	@Override
	public boolean removeEldestEntry(Map.Entry<K,V> eldest) {
//		System.out.println("即将根据LRU算法，删除最近最少使用元素：key= "+eldest.getKey()+" value= "+eldest.getValue()+" .");
		//此行代码是关键，一旦容量超出限制，即按照LRU进行删除
        return size()>capacity;
    } 
}
public class LRULinkedHashMapTest {

	public static void main(String[] args) {
		
		testLinkedHashMap();
//		testLRULinkedHashMap();

	}
	
	public static void testLinkedHashMap() {
		//容量固定，accessOrder=true
		Map<Integer, Integer> map = new LinkedHashMap<Integer, Integer>(3, 0.75f, true);
		map.put(1, 1);
		map.put(2, 2);
		map.put(3, 3);
		map.put(4, 4);
		map.put(5, 5);
		map.put(9, 9);

		//此时输出1,2,3,4,5
		for(Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); it.hasNext();) {
			System.out.println(it.next().getValue());
		}
		System.out.println("-----------------------------");

		map.put(4, 4);
		map.put(6, 6);

		//此时输出1,2,3,5,4,6
		for(Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); it.hasNext();) {
			System.out.println(it.next().getValue());
		}

	}
	
	public static void testLRULinkedHashMap() {
		//容量固定，accessOrder=true
		Map<Integer, Integer> map = new LRULinkedHashMap<Integer, Integer>(2);
		map.put(1, 1);
		map.put(2, 2);
		map.put(3, 3);
		map.put(4, 4);
		map.put(5, 5);

		for(Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); it.hasNext();) {
			System.out.println(it.next().getValue());
		}
		System.out.println("-----------------------------");

		map.put(4, 4);
		map.put(6, 6);

		for(Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); it.hasNext();) {
			System.out.println(it.next().getValue());
		}
		
	}
	
}
